/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/find-minimum-in-rotated-sorted-array
   @Language: C++
   @Datetime: 19-11-21 11:27
   */

// Time O(logn), Space O(1)
// The original array must sorted in ascending order
class Solution {
public:
	int findMin(vector<int>& nums) {
		for(int i=0, k, j=nums.size(); i<j;){
			if(i+1==j || nums[i]<nums[j-1]) return nums[i];
			k=(i+j)/2;
			if(i+1<k && nums[i]>nums[k-1]) j=k;
			else i=k;
		}
		return 0;
	}
};

